DROPS

Document

Invited Talk

DOI: 10.4230/LIPIcs.SOCG.2015.405

The Dirac-Motzkin Problem on Ordinary Lines and the Orchard Problem (Invited Talk)

Authors: Ben J. Green

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

Suppose you have n points in the plane, not all on a line. A famous theorem of Sylvester-Gallai asserts that there is at least one ordinary line, that is to say a line passing through precisely two of the n points. But how many ordinary lines must there be? It turns out that the answer is at least n/2 (if n is even) and roughly 3n/4 (if n is odd), provided that n is sufficiently large. This resolves a conjecture of Dirac and Motzkin from the 1950s. We will also discuss the classical orchard problem, which asks how to arrange n trees so that there are as many triples of colinear trees as possible, but no four in a line. This is joint work with Terence Tao and reports on the results of [Green and Tao, 2013].

Cite as

Ben J. Green. The Dirac-Motzkin Problem on Ordinary Lines and the Orchard Problem (Invited Talk). In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, p. 405, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{green:LIPIcs.SOCG.2015.405,
  author =	{Green, Ben J.},
  title =	{{The Dirac-Motzkin Problem on Ordinary Lines and the Orchard Problem}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{405--405},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.405},
  URN =		{urn:nbn:de:0030-drops-50852},
  doi =		{10.4230/LIPIcs.SOCG.2015.405},
  annote =	{Keywords: combinatorial geometry, incidences}
}

Search Results

Documents authored by Green, Ben J.

The Dirac-Motzkin Problem on Ordinary Lines and the Orchard Problem (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message